Definition

The competitive ratio of an algorithm is

maxσ⁡ALG(σ)OPT(σ)\max_\sigma \frac{ALG(\sigma)}{OPT(\sigma)}

References

  1. https://www.cs.cmu.edu/~avrim/451f13/lectures/lect1107.pdf